Data Structure 📄

Logical data structure uses physical data structure to implement itself.

Physical Data Structure

• How data is actually stored in memory(RAM, disk).
• Deals with the real-world representation.
• Involves memory management, allocation, data storage.
• Impact performance and access speed.
• Examples: Array, Linked List.

Logical Data Structure

• How data is conceptually organized and how operation performed on it.
• It define relationships, hierarchy.
• Examples: Stack, Queue.

Question

How to apply frequency array in negative value?

When you want to use a frequency array (counting array) but your values include negative numbers, the problem is that array indices can't be negative. So you need to shift the values to make them non-negative.

Core Idea: Offset (Shift) the Values

1. Find the minimum value in your data.
2. Use an offset = -min_value.
3. Add this offset to every element when indexing.

Suppose your array is:

[-5, -2, -5, 0, 3]

1. Find range

• min = -5
• max = 3

2. Create freq array

Size = max - min + 1 = 3 - (-5) + 1 = 9

3. Use offset

offset = -min = 5

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> arr = {-5, -2, -5, 0, 3};

    int min_val = arr[0], max_val = arr[0];

    // Find min and max
    for (int x : arr) {
        if (x < min_val) min_val = x;
        if (x > max_val) max_val = x;
    }

    int offset = -min_val;
    int size = max_val - min_val + 1;

    vector<int> freq(size, 0);

    // Count frequency
    for (int x : arr) {
        freq[x + offset]++;
    }

    // Print frequencies
    for (int i = 0; i < size; i++) {
        if (freq[i] > 0) {
            cout << "Value: " << i - offset 
                 << ", Count: " << freq[i] << endl;
        }
    }

    return 0;
}

Key Formula

• Index = value + offset
• Original value = index - offset

When NOT to use this

• If values are very large (e.g., -1e9 to 1e9), this approach wastes memory.
• In that case, use:

unordered_map<int, int> freq;